package demo10;


import java.util.ArrayList;

public class FindValUsingIndex {
    public Listy createListy(){
        return new Listy();
    }
    public class Listy{
        public int[] variableArray;

        public void setVariableArray(int[] variableArray) {
            this.variableArray = variableArray;
        }

        public int elemenetAt(int index){
            // 21 > 21 , false
            if(index>variableArray.length){
                return -1;
            }
            return variableArray[index-1];
        }
        // using binarySearch to find the length
        // use 1,2,4,8,16,32,64,128
        // first choose the left , choose the right
        // sencond choose middle , then using the binarySearch  to find the length ,
        // when the range is from 8 - 16 ,
        // 16
        // you can try to using foreach ? no ,using the  binarySearch to search
        //
        public int getIndex(int val ){
            int index=1;
            while (elemenetAt(index)!=-1){
                index = index<<1;
            }
            int start = index >>1;
            int end = index ;
            int i = binarySearchPos( val, start, end);
            return i;
        }
        // 16  + 32 =48 / 2 =24 > 21 ==-1  search the left ,and the high sholud be 23   16,23
        //  otherwise 19<21 , !=-1 find the ele from 19-32
        public int binarySearchPos(int val , int low ,int high){
            if(low<=high) {
                int middle = (low + high) / 2;
                if(elemenetAt(middle)>val || elemenetAt(middle)==-1){
                    return binarySearchPos (val,low,middle-1 );
                }else if (elemenetAt(middle)<val){
                    return binarySearchPos(val,middle+1,high  );
                }else{
                    return middle;
                }
            }
            return -1;
        }


    }
}
